package binaryTree.review;

public class QuickSort3 {

    public  int[]  quickSort(int[] nums){
        if (nums.length==0){
            return null;
        }
        sort(nums,0, nums.length-1);
         return nums;
    }


    public  void sort(int[] nums,int lo,int hi){
        if (lo >=hi) {
            return;
        }
        int partition = partition(nums, lo, hi);
        sort(nums,lo,partition-1);
        sort(nums,partition+1,hi);
    }

    public  int partition(int[] nums,int lo,int hi){
        int boundary=nums[lo];
        int j=lo+1;
        int k=hi;
        while (j<=k){
            while (j<=hi&&nums[j]<=boundary){
                j++;
            }
            while (k>lo&&nums[k]>boundary){
                k--;
            }
            if (j>k)
            {
                break;
            }
            swap(nums,j,k);
        }
        swap(nums,lo,k);

        return  k;


    }

    public  void  swap(int[] nums,int j,int k){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

    public static void main(String[] args) {
        QuickSort3 quickSort3 = new QuickSort3();
        int[] nums=new int[]{2,5,3,4,1,6};
        int[] sort = quickSort3.quickSort(nums);
        for (int a:sort
        ) {
            System.out.println(a);

        }
    }


}
